//
//  TTFastConvexHull.m
//  iBeaconDemo
//
//  Created by cry on 17/1/9.
//  Copyright © 2017年 eGova. All rights reserved.
//

#import "TTFastConvexHull.h"
#import "TTPointProbabilityMap.h"

@implementation TTFastConvexHull
static int const ONE = 1;
static int const TWO = 2;
static int const THREE = 3;

- (NSMutableArray<TTPointProbabilityMap *> *) computeHull:(NSArray<TTPointProbabilityMap *> *)points{
//    ArrayList<PointProbabilityMap> xSorted = (ArrayList<PointProbabilityMap>) points.clone();
    NSMutableArray<TTPointProbabilityMap *> *xSorted = [NSMutableArray arrayWithArray:points];
//    Collections.sort(xSorted, new XCompare());
    [xSorted sortUsingSelector:@selector(compareByX:)];
//    xSorted = [NSMutableArray a];
//    int n = xSorted.size();
    NSInteger n = xSorted.count;
//    PointProbabilityMap[] lUpper = new PointProbabilityMap[n];
    NSMutableArray<TTPointProbabilityMap *> *lUpper = [NSMutableArray arrayWithCapacity:n];
//    lUpper[0] = xSorted.get(0);
//    lUpper[1] = xSorted.get(1);
    lUpper[0] = xSorted[0];
    lUpper[1] = xSorted[1];
//    int lUpperSize = 2;
    NSInteger lUpperSize = 2;
//    
//    for (int i = 2; i < n; i++) {
    for (int i = 2; i < n; i++) {
//        lUpper[lUpperSize] = xSorted.get(i);
        lUpper[lUpperSize] = xSorted[i];
//        lUpperSize++;
        lUpperSize++;
//        while (lUpperSize > 2 && !rightTurn(lUpper[lUpperSize - FastConvexHull.THREE],
//                                            lUpper[lUpperSize - FastConvexHull.TWO],
//                                            lUpper[lUpperSize - FastConvexHull.ONE])) {
        while (lUpperSize > 2 && ![self rightTurnWithA:lUpper[lUpperSize - THREE]
                                                     B:lUpper[lUpperSize - TWO]
                                                     C:lUpper[lUpperSize - ONE]]) {
//            Remove the middle point of the three last
//            lUpper[lUpperSize - 2] = lUpper[lUpperSize - 1];
//            lUpperSize--;
            lUpper[lUpperSize - 2] = lUpper[lUpperSize - 1];
            lUpperSize--;
//        }
        }
//    }
    }
//    PointProbabilityMap[] lLower = new PointProbabilityMap[n];
//    lLower[0] = xSorted.get(n - 1);
//    lLower[1] = xSorted.get(n - 2);
    NSMutableArray<TTPointProbabilityMap *> *lLower = [NSMutableArray arrayWithCapacity:n];
    lLower[0] = xSorted[n - 1];
    lLower[1] = xSorted[n - 2];
//    int lLowerSize = 2;
    NSInteger lLowerSize = 2;
//    for (int i = n - FastConvexHull.THREE; i >= 0; i--) {
    for (NSInteger i = n - THREE; i >= 0; i--) {
//        lLower[lLowerSize] = xSorted.get(i);
//        lLowerSize++;
        lLower[lLowerSize] = xSorted[i];
        lLowerSize++;
//        while (lLowerSize > 2 && !rightTurn(lLower[lLowerSize - FastConvexHull.THREE],
//                                            lLower[lLowerSize - FastConvexHull.TWO],
//                                            lLower[lLowerSize - FastConvexHull.ONE])) {
        while (lLowerSize > 2 && ![self rightTurnWithA:lLower[lLowerSize - THREE]
                                                     B:lLower[lLowerSize - TWO]
                                                     C:lLower[lLowerSize - ONE]]) {
//            // Remove the middle point of the three last
//            lLower[lLowerSize - 2] = lLower[lLowerSize - 1];
//            lLowerSize--;
            lLower[lLowerSize - 2] = lLower[lLowerSize - 1];
            lLowerSize--;
        }
//    }
    }
//    ArrayList<PointProbabilityMap> result = new ArrayList<PointProbabilityMap>();
    NSMutableArray *result = [NSMutableArray array];
//    for (int i = 0; i < lUpperSize; i++) {
//        result.add(lUpper[i]);
//    }
    for (int i = 0; i < lUpperSize; i++) {
        [result addObject:lUpper[i]];
    }
//    for (int i = 1; i < lLowerSize - 1; i++) {
//        result.add(lLower[i]);
//    }
    for (int i = 1; i < lLowerSize - 1; i++) {
        [result addObject:lLower[i]];
    }
//    return result;
    return result;
}
/**
 * Right turn.
 *
 * @param a the a
 * @param b the b
 * @param c the c
 * @return true, if successful
 */
//    private boolean rightTurn(Point a, Point b, Point c) {
//        return (b.getX() - a.getX()) * (c.getY() - a.getY()) - (b.getY() - a.getY()) * (c.getX() - a.getX()) > 0;
//    }
/**
 *
 *  ┗|｀O′|┛  用来计算斜率差，判断三点的连线是不是凹形状
 *
 */
- (BOOL)rightTurnWithA:(TTPoint *)a B:(TTPoint *)b C:(TTPoint *)c{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) > 0;
}

@end
